//47. 全排列 II https://leetcode.cn/problems/permutations-ii/description/?envType=problem-list-v2&envId=array

class Solution {
    List<Integer> nums;
    List<List<Integer>> res;

    void swap(int a, int b) {
        int tmp = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, tmp);
    }
    //首先确定的是x是表示确定的第几个元素                横轴
    //set表示的是在第x个元素下的纵向有几个元素           纵轴
    //nums是最后返回的结果链表                          结果
    //i用来遍历nums组成的可能性                         筛选可能性
    void dfs(int x){
        //首先判断，当元素个数 横轴x 达到最终结果数时 返回结果
        if(x==nums.size()-1){
            res.add(new ArrayList<>(nums));
            return;
        } 
        HashSet<Integer> set = new HashSet<>();
        for(int i=x;i<nums.size();i++){
            //首先先判断该元素是不是在set中存在
            if(set.contains(nums.get(i))){
                continue;//重复减枝
            }
            set.add(nums.get(i));
            //交换，固定该元素
            swap(i,x);
            //固定下一个元素（进入回溯，知道在x=nums.size()-1，返回一个完整的nums）
            dfs(x+1);
            //逐一在回溯中还原nums，筛选可能性
            swap(i,x);
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.res = new ArrayList<>();
        this.nums = new ArrayList<>();
        for(int num : nums){
            this.nums.add(num);
        }
        dfs(0);
        return res;
    }
}

//11. 盛最多水的容器  https://leetcode.cn/problems/container-with-most-water/description/

class Solution {
    public int maxArea(int[] height) {
        //双指针
        int left = 0;
        int right = height.length-1;
        int s=0;
        while(left<right){
            s=Math.max(s,(right-left)*Math.min(height[left],height[right]));
            if(height[left]<height[right]){
                left++;
            }else{
                right--;
            }
        }
        return s;
    }
}

//414. 第三大的数   https://leetcode.cn/problems/third-maximum-number/description/

class Solution {
    public int thirdMax(int[] nums) {
        // 使用Long.MIN_VALUE避免与整数最小值冲突
        long firstMax = Long.MIN_VALUE;
        long secondMax = Long.MIN_VALUE;
        long thirdMax = Long.MIN_VALUE;
        
        // 用Set去重
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        // 遍历去重后的元素，更新三大最大值
        for (int num : set) {
            if (num > firstMax) {
                // 新元素成为第一大，原来的第一、第二顺次后移
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = num;
            } else if (num > secondMax) {
                // 新元素成为第二大，原来的第二顺次为第三
                thirdMax = secondMax;
                secondMax = num;
            } else if (num > thirdMax) {
                // 新元素成为第三大
                thirdMax = num;
            }
        }
        
        // 如果第三大仍为初始值（说明元素不足3个），返回最大值
        return thirdMax == Long.MIN_VALUE ? (int) firstMax : (int) thirdMax;
    }
}